package com.linyaonan.leetcode.medium._1282;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 *
 * 有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。
 *
 * 你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：groupSizes = [3,3,3,3,3,1,3]
 * 输出：[[5],[0,1,2],[3,4,6]]
 * 解释：
 * 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
 * 示例 2：
 *
 * 输入：groupSizes = [2,1,3,3,3,2]
 * 输出：[[1],[0,5],[2,3,4]]
 *  
 *
 * 提示：
 *
 * groupSizes.length == n
 * 1 <= n <= 500
 * 1 <= groupSizes[i] <= n
 *
 *
 * @author: Lin
 * @date: 2020/1/14
 */
public class GroupThePeople {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        HashMap<Integer, Integer> people = new HashMap<>();
        List<List<List<Integer>>> result = new ArrayList<>();
        int putIndex = 0;
        for (int i = 0; i < groupSizes.length; i++) {
            int v = groupSizes[i];
            if (people.containsKey(v)) {
                Integer index = people.get(v);
                List<List<Integer>> list = result.get(index);
                List<Integer> last = list.get(list.size() - 1);
                if (last.size() == v) {
                    List<Integer> add = new ArrayList<>();
                    add.add(i);
                    list.add(add);
                } else {
                    last.add(i);
                }
            } else {
                people.put(v, putIndex++);
                List<Integer> list = new ArrayList<>();
                list.add(i);
                List<List<Integer>> re = new ArrayList<>();
                re.add(list);
                result.add(re);
            }
        }
        List<List<Integer>> real = new ArrayList<>();
        for (List<List<Integer>> lists : result) {
            real.addAll(lists);
        }
        return real;
    }
}
